package com.gitee.feizns.explore.data_structure.tree.bs.mid;

import java.util.Arrays;
import java.util.stream.Stream;

/**
 * 449. 序列化和反序列化二叉搜索树
 * @author feizns
 * @since 2020/3/10
 */
public class Codec {

    public static void main(String[] args) {
        TreeNode ret = buildTree(new int[]{2, 1, 3}, 0, 2);
        System.out.println(ret);
        System.out.println(new Codec().serialize(ret));
        System.out.println(new Codec().serialize(ret));
    }

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if ( root != null ) {
            return preOrder(root, new StringBuilder()).toString();
        }
        return "";
    }

    private StringBuilder preOrder(TreeNode root, StringBuilder builder) {
        if ( root != null ) {
            builder.append(root.val);
            builder.append(",");
            preOrder(root.left, builder);
            preOrder(root.right, builder);
        }
        return builder;
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if ( data != null && !data.trim().isEmpty() ) {
            int[] ret = Arrays.stream(data.split(",")).mapToInt(Integer::valueOf).toArray();
            return buildTree(ret, 0, ret.length - 1);
        }
        return null;
    }

    private static TreeNode buildTree(int[] ret, int l, int r) {
        TreeNode re = null;
        if ( l == r )
            re = new TreeNode(ret[l]);
        else if ( l < r ) {
            re = new TreeNode(ret[l]);
            int i = l + 1;
            for (; i <= r && ret[i] < ret[l]; i++) { }
            re.left = buildTree(ret, l + 1, i - 1);
            re.right = buildTree(ret, i, r);
        }
        return re;
    }

}
